package com.atguigu.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author RuiKnag
 * @create 2021-05-31-17:22
 */
/*
 * (贪心算法)贪婪算法是指在对问题进行求解的时，在每一步选择中都采取最好或者最优的选择，
 * 从而希望能够导致结果最好的或者最优的算法。
 * 得到的结果不一定最优，但是接近最优的结果。
 * */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //创建广播电台，放入到map中
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        HashSet<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");
        HashSet<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("深圳");
        HashSet<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");
        HashSet<String> set4 = new HashSet<>();
        set4.add("上海");
        set4.add("天津");
        HashSet<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");
        broadcasts.put("k1",set1);
        broadcasts.put("k2",set2);
        broadcasts.put("k3",set3);
        broadcasts.put("k4",set4);
        broadcasts.put("k5",set5);
        //创建一个allAreas存放所有地区
        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("深圳");
        allAreas.add("广州");
        allAreas.add("成都");
        allAreas.add("上海");
        allAreas.add("杭州");
        allAreas.add("大连");
        allAreas.add("天津");
        //定义一个集合存放我们选择的电台
        ArrayList<String> select = new ArrayList<>();
        //定义一个临时集合，在遍历的过程中，存放遍历过程中 电台覆盖的地区 和还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<>();
        //顶一个一个maxKey，用来表示在本轮所覆盖的最多地区的电台
        String maxKey=null;
        while (allAreas.size()>0){
            maxKey=null;
            //遍历当前的电台
            for (String key:broadcasts.keySet()) {
                tempSet.clear();
                //用来存放当前的电台覆盖区域
                tempSet.addAll(broadcasts.get(key));
                //求当前电台和未覆盖的地区的交集
                tempSet.retainAll(allAreas);
                if(tempSet.size()>0&&(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){
                    maxKey=key;
                }
            }
            if(maxKey!=null){
                select.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }
        System.out.println("最终结果为"+select);
    }
}
